优先级队列.java

/** 
 * 用堆实现一个优先级队列 
 * 主要是添加、修改、删除节点 
 * 节点具有唯一性 
 * @author HHF 
 * 2014年11月28日 
 */  
public class PriorityQueue {  
  
    public static int HEAPSIZE;  
    public static void main(String[] args) {  
        int[] array = Common.random(0,100,10);  
        HEAPSIZE = array.length;  
        build(array);//建一个极大堆  
        System.out.println("原始数据：");  
        Common.print(array);  
      
        //获得最大值  
        System.out.println("优先级最高的节点："+maximum(array));  
          
        //获得并删除最大值  
        System.out.println("将要被删除的优先级最高的节点："+extractMax(array));  
        System.out.println("删除后的数据：");  
        Common.print(array);  
          
        //修改优先级  
        increaseKey(array, 5, 100);  
        System.out.println("修改后的数据：");  
        Common.print(array);  
          
        //添加节点  
        insert(array, 101);  
        System.out.println("插入后的数据：");  
        Common.print(array);  
          
        //删除节点  
        System.out.println("删除的数据："+delete(array, 1));  
        System.out.println("删除后的数据：");  
        Common.print(array);  
    }  
      
    /** 
     * 返回优先队列中优先级最高的节点 
     * @param array 
     * @return 
     */  
    public static int maximum(int[] array){  
        return array[0];  
    }  
      
    /** 
     * 去掉并返回优先级队列中优先级最高的节点 
     * @param array 
     * @return 
     */  
    public static int extractMax(int[] array){  
        if(HEAPSIZE < 1){  
            (new Exception("队列内无元素    ")).printStackTrace();  
            return 0;  
        }  
        //获得最优节点  
        int max = array[0];  
        //删除最优节点  
        array[0] = array[--HEAPSIZE];  
        //整理堆  
        heapify(array, 0);  
        //返回最优节点值  
        return max;  
    }  
      
    /** 
     * 往优先队列中插入节点 
     * 记得要去重 
     * @param array 
     * @param x 
     */  
    public static void insert(int[] array, int x){  
        array[HEAPSIZE++] = x-1;//加一个元素  
        increaseKey(array, HEAPSIZE-1, x);  
    }  
      
    /** 
     * 将优先级为x的节点优先级修改为k 
     * @param array 
     * @param i被修改值下标 
     * @param k 
     */  
    public static void increaseKey(int[] array, int i, int k){  
        if(HEAPSIZE <= i){  
            (new Exception("修改优先级节点下标有误  ")).printStackTrace();  
            return;  
        }  
        if(k <= array[i]){  
            (new Exception("新节点的优先级被改低了  ")).printStackTrace();  
            return;  
        }  
        //优先级被修改了  
        array[i] = k;  
        //整理队列  
        int parent = (i-1)/2; //父节点下标  
        while(parent>-1 && array[parent]<array[i]){//到了必要交换子父节点的时候了  
            Common.swap(array, parent, i);  
            i = parent;  
            parent = (i-1)/2;  
        }  
    }  
      
    /** 
     * 将下标为i的节点删除 并返回其值 
     * @param array 
     * @param i 
     */  
    public static int delete(int[] array, int i){  
        if(HEAPSIZE <= i){  
            (new Exception("删除节点下标有误  ")).printStackTrace();  
            return 0;  
        }  
        //优先级被修改了  
        int result = array[i];  
        //整理队列  
        array[i] = -1;  
        heapify(array, i);  
        HEAPSIZE--;  
        return result;  
    }  
      
    /** 
     * 将array变成一个极大堆 
     * @param array 堆 
     */  
    public static void build(int[] array){  
        int size = array.length;  
        for(int i=size/2-1; i>=0; i--){  
            heapify(array, i);  
        }  
    }  
      
    /** 
     * 前提是i的左右孩子子树均已经为正常极大堆 
     * 将i调整为正确位置 
     * @param array 
     * @param i 下标 
     */  
    public static void heapify(int[] array, int i){  
        int left = 2*i+1;//左孩子下标  
        int right = left+1;//右孩子下标  

        int large = 0;  
        //选出left right 和  i 三个下标对应的最大值 记其下标为large   
        if(left < HEAPSIZE  && array[left] > array[i]){  
            large = left;  
        }else{  
            large = i;  
        }  
        if(right < HEAPSIZE && array[right] > array[large]){  
            large = right;  
        }  
        //准备发生交换 和 递推下一轮  
        if(large != i){  
            swap(array, large, i);  
            heapify(array, large);//此时的i所对应的值 已经 下移一层到了large  
        }  
    }  
}  